package leetcodev1.数组;

public class LeetCode79 {

    boolean ret = false;
    int rows, columns;

    public boolean exist(char[][] board, String word) {
        this.rows = board.length;
        this.columns = board[0].length;
        boolean[][] visited = new boolean[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                helper(board, i, j, 0, visited, word);
                if (ret) {
                    return true;
                }
            }
        }
        return ret;
    }

    private void helper(char[][] board, int x, int y, int index, boolean[][] visited, String word) {
        if (x < 0 || x >= rows || y < 0 || y >= columns) {
            return;
        }

        if (visited[x][y]) {
            return;
        }

        if (board[x][y] != word.charAt(index)) {
            return;
        }

        if (index == word.length() - 1) {
            ret = true;
            return;
        }

        visited[x][y] = true;
        //向上
        helper(board, x - 1, y, index + 1, visited, word);
        //向下
        helper(board, x + 1, y, index + 1, visited, word);
        //向左
        helper(board, x, y - 1, index + 1, visited, word);
        //向右
        helper(board, x, y + 1, index + 1, visited, word);
        visited[x][y] = false;
    }
}
